// 打印1到最大的n位数
// 这是一个大数问题，long long都无法容纳这个最大数。采用字符串模拟数字加法或减法

// 1、每一次为字符串表示的数字+1,
// 2、打印出来；
#include <iostream>
#include <string.h>
#include <cstdlib>
#include <ctime>

using namespace std;

bool Increment(char * number)
{
    bool isOverflow = false;      // 标志是否达到最高位
    int nTakeOver = 0;            // 标志是否进位
    int nLength = strlen(number); // 字符串长度

    for(int i = nLength - 1; i >= 0; i--)
    {
        int nSum = number[i] - '0' + nTakeOver;
        if (i == nLength - 1)     // 每次+1
            nSum ++;
        if (nSum >= 10)           // 如果该为>10则进位
        {
            if (i == 0)           // 如果此时i在最高位，无法进位，溢出
                isOverflow = true;
            else
            {
                nSum -= 10;       // 进位后，减10操作
                nTakeOver = 1;    // 进位标志 1
                number[i] = '0' + nSum;  // 第i位的数字
            }
        }
        else
        {
            number[i] = '0' + nSum; // 如果不进位，正常加减操作，并且跳出循环。因为该轮已经结束
            break;
        }
    }
    return isOverflow;
}

void PrintNumber(char * number)
{
    bool isBegining = true;
    int nLength = strlen(number);
    for(int i = 0; i < nLength; ++ i)
    {
        if (isBegining && number[i] != '0')
            isBegining = false;
        if (!isBegining)
            cout << number[i];
    }
    cout << " ";
}

void Print1ToMaxOfNDigits(int n)
{
    if (n <= 0)
        return;

    char * number = new char [n + 1];
    memset(number, '0', n);
    number[n] = '\0';
    int i = 0;
    while (!Increment(number))
    {
        if (++i % 10 == 0)
            cout << endl;
        PrintNumber(number);
    }

    delete [] number;
}


// 问题转换成数字排列的问题，n位所有十进制其实就是n个从0到9的全排列
// niubility
void Print1ToMaxOfNDigits_Recursively(char * number, int length, int index)
{
    if (index == length - 1)
    {
        PrintNumber(number);
        return;
    }
    // 第index + 1位从0~9的排列
    for(int i = 0; i < 10; ++ i)
    {
        number[index + 1] = i + '0';
        Print1ToMaxOfNDigits_Recursively(number, length, index + 1);
    }
}

void Print1ToMaxOfNDigits2(int n)
{
    if (n <= 0)
        return;

    char * number = new char [n + 1];
    number[n] = '\0';
    
    // 第1位从0~9的排列
    for(int i = 0; i < 10; ++ i)
    {
        number[0] = i + '0';
        Print1ToMaxOfNDigits_Recursively(number, n, 0);
    }
    delete [] number;
}

int main(int argc, char * argv[])
{
    clock_t startTime, endTime;
    int n = -1;
    startTime = clock();
    Print1ToMaxOfNDigits2(n);
    endTime = clock();
    cout << "Total time: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << endl;
    return 0;
}
